/*
 * File:   TestMergeSort.cpp
 * Author: marco
 *
 * Created on December 7, 2009, 12:59 PM
 */

#include <alg/MergeSort.h>
#include <alg/InPlaceComparer.h>
#include <alg/IteratorComparer.h>
#include <gtest/gtest.h>
#include <algorithm>


TEST(MergeSortTest, TestOneElement) {
    std::vector<std::size_t> v;
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
}

TEST(MergeSortTest, TestTwoElementsSorted) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
}

TEST(MergeSortTest, TestTwoElementsUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(2);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
}

TEST(MergeSortTest, TestFourElementsUnsorted1) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);
    v.push_back(3);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
}

TEST(MergeSortTest, TestFourElementsUnsorted2) {
    std::vector<std::size_t> v;
    v.push_back(3);
    v.push_back(2);
    v.push_back(4);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
}

TEST(MergeSortTest, TestFullyUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
}

TEST(MergeSortTest, TestRepetitionsUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    v.push_back(4);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(1, v[1]);
    EXPECT_EQ(2, v[2]);
    EXPECT_EQ(2, v[3]);
    EXPECT_EQ(3, v[4]);
    EXPECT_EQ(4, v[5]);
}

TEST(MergeSortTest, TestBlockSorted) {
    std::vector<std::size_t> v;
    v.push_back(5);
    v.push_back(6);
    v.push_back(3);
    v.push_back(4);
    v.push_back(1);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
    EXPECT_EQ(5, v[4]);
    EXPECT_EQ(6, v[5]);
}

TEST(MergeSortTest, TestOddSize) {
    std::vector<std::size_t> v;
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
}

TEST(MergeSortTest, TestOutOfPlace) {
    std::vector<int> values;
    values.push_back(3);
    values.push_back(2);
    values.push_back(4);
    values.push_back(1);
    std::vector<std::size_t> indexes;
    indexes.push_back(0);   // 3
    indexes.push_back(1);   // 2
    indexes.push_back(2);   // 4
    indexes.push_back(3);   // 1
    alg::IteratorComparer<std::vector<int> > comparer(values);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(indexes, comparer);
    mergeSort.sort();
    EXPECT_EQ(3, indexes[0]);
    EXPECT_EQ(1, values.at(indexes[0]));
    EXPECT_EQ(1, indexes[1]);
    EXPECT_EQ(2, values.at(indexes[1]));
    EXPECT_EQ(0, indexes[2]);
    EXPECT_EQ(3, values.at(indexes[2]));
    EXPECT_EQ(2, indexes[3]);
    EXPECT_EQ(4, values.at(indexes[3]));
}

TEST(MergeSortTest, TestPerformance) {
    std::vector<std::size_t> v;
    for (int i = 18999; i >= 0; --i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(10000);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::MergeSort<std::vector<std::size_t> > mergeSort(v, comparer);
    mergeSort.sort();
    EXPECT_EQ(0, v[0]);
    EXPECT_EQ(0, v[1]);
    EXPECT_EQ(1, v[2]);
    EXPECT_EQ(1, v[3]);
    EXPECT_EQ(2, v[4]);
    EXPECT_EQ(2, v[5]);
    EXPECT_EQ(500, v[1000]);
    EXPECT_EQ(1000, v[2000]);
    EXPECT_EQ(1001, v[2001]);
    EXPECT_EQ(1002, v[2002]);
    EXPECT_EQ(8999, v[9999]);
    EXPECT_EQ(10000, v[11000]);
    EXPECT_EQ(10000, v[12000]);
    EXPECT_EQ(10001, v[12001]);
    EXPECT_EQ(18999, v[20999]);
}

TEST(MergeSortTest, TestStdPerformance) {
    std::vector<std::size_t> v;
    for (int i = 18999; i >= 0; --i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(10000);
    // uses merge sort algorithm
    std::stable_sort(v.begin(), v.end());
    EXPECT_EQ(0, v[0]);
    EXPECT_EQ(0, v[1]);
    EXPECT_EQ(1, v[2]);
    EXPECT_EQ(1, v[3]);
    EXPECT_EQ(2, v[4]);
    EXPECT_EQ(2, v[5]);
    EXPECT_EQ(500, v[1000]);
    EXPECT_EQ(1000, v[2000]);
    EXPECT_EQ(1001, v[2001]);
    EXPECT_EQ(1002, v[2002]);
    EXPECT_EQ(8999, v[9999]);
    EXPECT_EQ(10000, v[11000]);
    EXPECT_EQ(10000, v[12000]);
    EXPECT_EQ(10001, v[12001]);
    EXPECT_EQ(18999, v[20999]);
}
